package com.zjw.algorithm.ready1;

import java.util.Arrays;

public class _快速排序 {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _快速排序().sortArray(new int[]{5, 2, 3, 1})));
        System.out.println(Arrays.toString(new _快速排序().sortArray(new int[]{5, 1, 1, 2, 0, 0})));
    }

    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        qSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int lp = start - 1;
        int rp = end + 1;
        //哨兵
        int pivot = nums[(start + end) >> 1];

        while (lp < rp) {

            //找出第一个大于哨兵的值
            do {
                lp++;
            } while (nums[lp] < pivot);


            //找出第一个小于等于哨兵的值
            do {
                rp--;
            } while (nums[rp] > pivot);

            if (lp < rp) {
                //swap;
                int temp = nums[lp];
                nums[lp] = nums[rp];
                nums[rp] = temp;
            }

        }

        qSort(nums, start, rp);
        qSort(nums, rp + 1, end);
    }
}
